Batch 2 - Class 69 - Changing a Dollar (Recursion)

• (Geoffrey - 161 Modified) The sketch below shows the plan of industrial establishment with secret weapons. There are only three gates which are guarded. There is some information leakage, and they found this note supposedly written for the spy

• Answer: this is same as ways of arranging a number of 1's in a bit string. Since 210 appears as 5th number in 11th row, it must be at intersection of 7th and 5th Street (there is only one such combination above - if it was a larger grid, there would be two possibilities)
• 

     

  

• How many ways are there to make change for a dollar? No, really, think about it before moving on to the next problem. Even if you don't have a method, at least list a few ways, make a reasonable estimate with a reason for your estimate, and so on.
• OK, let's simplify the problem. How many ways are there to make change for a dollar if the only coins in the world are pennies?
• Now what if there are nickels and pennies?
• Can you generalize: how many ways are there to make n cents using only nickels and pennies?
• Now what if there are dimes, nickels, and pennies? It might help to make an organized table, of the ways of making each amount up to a dollar (maybe in multiples of 5 cents) using dimes, nickels and pennies.

  Instructor Notes: Introduce the notion of recursion, and walk students through how to think about it. Help them arrive at P(n)=1; N(n)=P(n)+N(n-5); D(n)=N(n)+D(n-10) with all values being 1 for n=0 and 0 for n<0Help organize a table to illustrate how this works on a board
• Now add in quarters. Do you want to allow half dollars? Dollar coins?

  See if students can get to Q(n)=D(n)+Q(n-25) by themselvesHelp organize a table to illustrate how this works on a boardHelp organize the same thing on an Excel spreadsheetAnswer with up to quarters is 242Ask kids what they would do with half dollars and dollars
• What if each arrangement (permutation) of the coins was counted differently? What would you have to change to produce the other answer 

  Let students think about how to account for all permutationsIf they are unable to think through, help them get to a conclusion that we can "reduce" the problem just by looking at what the first coin isHelp them arrive at equivalent formulae, and work through some entries on the boardHelp them organize it on an Excel sheetWow! the answers here, with up to quarters, goes to 9+ Trillion!

• "Tweet" is a 140 character post
• Ask kids to guess how much time would it take for the world to read all possible tweets
• So if we were using 26 alphabets and blank space, then for each position, we could have 27 choices, hence 27^140 tweets - roughly 10^100
• But we could have more characters. With 256 possibilities in each character (why?) you could get to 10^800
• Can you write a few of those - most would turn out to be junk
• How many of these could be legible english?

  What if English language had only 2 valid sentences - how many bits did we need to represent them?Points to "information content" in a sentenceLets consider the sentence "Oh my God, What are we doing!" - what is the information content in the word GodClose to zeroClaude Shannon showed people valid sentences cut at random points, and asked people to guess which letter came next. Based on correct guesses, he determined that information content of typical written english is 1-1.2 bits/letterGood compression algorithms should be able to compress english language (8 bits per character) to 1-1.2 bitsSince n bits of information can convey 2^n messages. So 140 characters should be able to convery about 2^(140x1.1) meaningful tweets, which is about 2*10^46
• How long would it take the world to read them out

  Lets assume we can read one tweet per 5 seconds3600 seconds to an hour, so 31M per year, across 7B people is about 4x10^16 tweets per year globallySo about 10^30 years - how much is that?

• (Matt Enlow's Rectangle Division Puzzle)  What is the fewest number of squares into which you can divide an 11 x 12 rectangle? What about a 12 x 13 rectangle? What about an 11 x 13 rectangle?

  Answer: 

  

• Let us start with a simpler problem - Lets write all number as sum of one square. Draw a table where for each number, we write down number of ways in which that number can be written as sum of one squares

  Of course, only perfect squares can be written, so their values will be 1 and others will be zero
• Now how do we write the next row -i.e. expressing numbers as sum of two squares?
• How about the third and fourth rows?
• Notice that by the time we come to the fourth row, all numbers have a way of writing them as sum of squares. Can you prove it?
• What have we counted - number of arrangements or choices?

  What if you were to count for choices (not permutations) - how would you approach it?